\section{Introduction}
\label{sec:intro}
Othello, also known as Reversi, is a well known and popular two player strategy game.  This popularity is not just limited to casual game players, but extends to the world of AI game researchers.  These researchers have taken an interest in Othello in part because of its structural similarity chess (e.g., an 8 $\times$ 8 board) yet relative simplicity when considering the game tree size.  Thus advancements in game tree search and heuristics can be developed for Othello and then adapted to the more complex chess~\cite{Jiang:2003}.

This is not to suggest that advancements in Othello are purely for chess.  Othello itself has been deeply researched with many powerful players developed (e.g.,~\cite{Lee:1990}\cite{Rosenbloom:1982}).  The culmination of this work is the 1997 defeat of Takeshi Murakami, the Othello world champion at the time, by LOGISTELLO which won all six games they played~\cite{Buro:match:1997}.

Our project goal is to leverage some of the ideas used in these players to develop our own agents for playing Othello.  We conducted a literature search on ideas for good Othello heuristic functions~\cite{Buro:2003}
\cite{Chong:2003}\cite{Kim:2007}\cite{mandt}\cite{Yoshioka:1999} and advancements in game tree search\cite{Buro:Probcut:1995}\cite{Buro:2002}\cite{Runarsson:2007}.  Even with these ideas to build from, we do not expect a world championship player in approximately four weeks.  Given that we must construct an Othello game framework which our agents can play in, our more realistic expectation is to build an agent that can defeat simple agents, much like ourselves, with efficiency and regularity.  To evaluate this progress, we have staged a tournament between our agents in our framework to determine which dominates the others and recorded statistics on their searches.

The rest of this report is organized as follows: we introduce concepts relevant to Othello and our Othello agents in Section~\ref{sec:bg}.  In Section~\ref{sec:arch} we discuss the architecture of our Othello game framework.  In Section~\ref{sec:search_algs} we present the implementation of our game tree search algorithms which use the heuristics we describe in Section~\ref{sec:heuristics}.  Our tournament results and efficiency metrics discussed in Section~\ref{sec:eval}.  Finally, we present work related to construction of Othello game agents in Section~\ref{sec:related_work}. 



%  Othello, also known as Reversi, has been a popular game since its invention in the 19th century~\cite{wiki:reversi}.  
  
  
  
%  What are my points?
%  Fun popular game with nice properties
%  Has been explore by AI community
%  Worthy for us to look at
%  
%  What did we want to explore/do?
%  Wanted to develop Othello game with agents good enough to beat us
%  Determine what agent/strategy was best through tournament play
%  
%  What did we do?
  
  

